{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 作业"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using matplotlib backend: Qt5Agg\n"
     ]
    }
   ],
   "source": [
    "%matplotlib"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 冒泡排序法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.animation as animation\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "def generator():\n",
    "    for i in range(1,len(arr)+1):\n",
    "        for j in range(0,len(arr)-i):\n",
    "            if arr[j]>arr[j+1]:\n",
    "                arr[j],arr[j+1]=arr[j+1],arr[j]\n",
    "                yield arr\n",
    "        lines[len(arr)-i].set_color('b')\n",
    "        lines2[len(arr)-i].set_color('b')\n",
    "        yield arr\n",
    "\n",
    "\n",
    "def update(datag):\n",
    "    for i in range(len(datag)):\n",
    "        lines[i].set_ydata([0, datag[i]])\n",
    "        lines2[i].set_ydata([0, datag[i]])\n",
    "\n",
    "    return lines\n",
    "\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "arr = [30, 8, 10, 9, 6, 4, 16, 5, 13, 26, 18, 2, 45, 34, 23, 1, 7, 3]\n",
    "n = len(arr)\n",
    "xdata = [[i+1 for i in range(n)], [i+1 for i in range(n)]]\n",
    "ydata = [[0 for i in range(n)], arr]\n",
    "\n",
    "ax.set_xticks([i+1 for i in range(n)])\n",
    "lines = ax.plot(xdata, ydata, linewidth=2, color='r')\n",
    "lines2 = ax.plot(xdata, ydata, 'ro', markersize=4)\n",
    "\n",
    "ani = animation.FuncAnimation(fig, update, generator, interval=300,repeat=False)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 快速排序法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.animation as animation\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "def quick_sort(num, l, r):\n",
    "    if l >= r:\n",
    "        if l >= len(lines):\n",
    "            l = len(lines) - 1\n",
    "        if r >= len(lines):\n",
    "            r = len(lines) - 1\n",
    "        lines[l].set_color('b')\n",
    "        lines2[l].set_color('b')\n",
    "        lines[r].set_color('b')\n",
    "        lines2[r].set_color('b')\n",
    "        yield num\n",
    "        return\n",
    "    flag = l\n",
    "\n",
    "    for i in range(l + 1, r + 1):\n",
    "        if num[flag] > num[i]:\n",
    "            tmp = num[i]\n",
    "            for j in range(i, flag, -1):\n",
    "                num[j] = num[j - 1]\n",
    "            num[flag] = tmp\n",
    "            lines[flag].set_color('r')\n",
    "            lines2[flag].set_color('r')\n",
    "            lines[flag+1].set_color('y')\n",
    "            lines2[flag+1].set_color('y')\n",
    "            flag += 1\n",
    "            yield num\n",
    "    yield num\n",
    "\n",
    "    for m in quick_sort(num, l, flag - 1):\n",
    "        yield m\n",
    "    lines[flag].set_color('b')\n",
    "    lines2[flag].set_color('b')\n",
    "    for n in quick_sort(num, flag + 1, r):\n",
    "        yield n\n",
    "\n",
    "\n",
    "def update(data_gen):\n",
    "    for i in range(len(data_gen)):\n",
    "        lines[i].set_ydata([0, data_gen[i]])\n",
    "        lines2[i].set_ydata([0, data_gen[i]])\n",
    "\n",
    "    return lines\n",
    "\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "arr = [12, 8, 10, 9, 6, 4, 16, 5, 13, 26, 18, 2, 45, 34, 23, 1, 17, 3]\n",
    "n = len(arr)\n",
    "\n",
    "xdata = [[i + 1 for i in range(n)], [i + 1 for i in range(n)]]\n",
    "ydata = [[0 for i in range(n)], arr]\n",
    "\n",
    "ax.set_xticks([i + 1 for i in range(n)])\n",
    "lines = ax.plot(xdata, ydata, linewidth=2, color='r')\n",
    "lines2 = ax.plot(xdata, ydata, 'ro', markersize=4)\n",
    "\n",
    "ani = animation.FuncAnimation(fig, update, quick_sort(arr, 0, len(arr) - 1), interval=300, repeat=False)\n",
    "plt.show()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
